package com.wenhao.dewu;

/**
 * @author Wenhao Tong
 * @create 2021-08-29 19:36
 */
public class Main3 {
    /**
     * 返回从源字符串到目标字符串的最小操作数
     * source: 源字符串
     * target：目标字符串
     * 返回：最小操作数
     */
    public int minOperationCount(String source, String target) {
        int[][] dp = new int[source.length() + 1][target.length() + 1];
        for (int i = 0;i < dp.length;i++) {
            dp[i][0] = i;
        }
        for (int j = 0;j < dp[0].length;j++) {
            dp[0][j] = j;
        }
        for (int i = 1;i < dp.length;i++) {
            for (int j = 1;j < dp[i].length;j++) {
                if (source.charAt(i - 1) == target.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j],dp[i][j - 1]),dp[i - 1][j - 1]);
                }
            }
        }
        return dp[source.length()][target.length()];
    }
}
